import java.util.HashMap;
import java.util.Map;

public class Test1 {
    public int lenLongestFibSubseq(int[] arr) {
        //首先根据经验定义dp表，dp[i]表示以第i个位置为结尾的所有子序列中最长的斐波拉契子序列的长度
        //但是当推导出状态转移方程的时候，我们无法通过已有的状态推导出dp[i]，所以我们可以定义一个二维的dp数组
        //然后dp[i][j]则表示以第i，j个位置为结尾的所有子序列中最长斐波拉契子序列的长度
        //每次固定j的位置，然后让i在[1,i)之间移动，每次移动到新的位子，就看前面是否有可以构成斐波拉契的子序列
        //如果有，那么dp[i][j] = dp[k][i] + 1;
        int  n = arr.length;
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                dp[i][j] = 2;
        Map<Integer,Integer> hash = new HashMap<>();
        for (int i = 0; i < n; i++) hash.put(arr[i],i);
        int ret = 2;
        for (int j = 2; j < n; j++) {
            for (int i = 1; i < j; i++) {
                if (arr[j] - arr[i] < arr[i] && hash.containsKey(arr[j] - arr[i])) {
                    dp[i][j] = Math.max(dp[i][j],dp[hash.get(arr[j] - arr[i])][i] + 1);
                    ret = Math.max(ret,dp[i][j]);
                }
            }
        }

        return ret >= 3 ? ret : 0;
    }
}
